#include<stdio.h>
#define INF 2000000000

int root(int n,int k)
{
	int i;
 while(n>=k) {
	 i=0;
  while(n!=0)
  {
   i+=n%k;
   n=n/k;
 }
  n=i;}
 return n;
}

int main()
{
 int x,y,k;
 int i;
 int n=1;
 while(scanf("%d%d%d",&x,&y,&k)==3&&x<INF&&y<INF&&x>0&&y>0&&k>2&&k<16)
 {
  for(i=0;i<y;i++)
  {	  n*=x;
      n=root(n,k);}
  printf("%d\n",n);
 }
 return 0;
}
//time limit exceed
